import random

def generate_sorted_array(length=None, min_val=-1000, max_val=1000):
    """生成随机有序数组"""
    if length is None:
        length = random.randint(0, 20)  # 随机长度，包括空数组
    
    if length == 0:
        return []
    
    # 生成随机不重复的元素
    elements = random.sample(range(min_val, max_val + 1), length)
    # 排序
    elements.sort()
    return elements

def generate_test_cases(num_cases=10):
    """生成多个测试用例"""
    test_cases = []
    # 包含特殊情况
    test_cases.append([])  # 空数组
    test_cases.append([0])  # 单元素
    test_cases.append([1, 2])  # 双元素
    test_cases.append([1, 2, 3])  # 三元素
    test_cases.append([-10, -3, 0, 5, 9])  # 示例用例
    
    # 生成随机测试用例
    for _ in range(num_cases - len(test_cases)):
        test_cases.append(generate_sorted_array())
    
    return test_cases

def tree_to_list(root):
    """将二叉树转换为层序遍历列表，用于测试验证"""
    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    
    # 移除末尾的None
    while result and result[-1] is None:
        result.pop()
    
    return result    